This invention relates to computer storage systems and more particularly to computer storage systems including a virtual memory system for converting a virtual address to a real physical address.
Various techniques are known whereby several computer programs, executed either by a single central processing unit or by a plurality of processing units, share one memory. A memory being shared by programs in this manner requires an extremely large storage capacity, a capacity which is often larger than its actual capacity. To accommodate this situation the concept of "virtual storage" is employed. If, for example, a system employs a 24 bit addressing scheme 2.sup.24 bytes or approximately sixteen million addressable bytes of virtual storage are available. This virtual storage is divided into segments each of which is divided into pages, with each page consisting of a predetermined number of bytes. The segment and page addresses assigned to virtual storage are arbitrary programming designations and are not actual locations in main storage. Therefore, virtual segments and pages can be located randomly throughout main storage and swapped in and out of main storage as they are needed.
Random location of segments and pages in main storage necessitates the translation of virtual address into actual address using a set of conversion tables that are located in main storage. In a virtual memory system a number of sets of conversion tables are employed, each made up of a segment table and a number of page tables. Each page table in a set of conversion tables reflects the real locations of all the pages of one segment in the segment table. Therefore, if a particular segment table is divided into 16 segments, there would be 16 page tables and one segment table in the set of conversion tables in performing a translation.
In making a translation, the proper set of conversion tables is selected and the segment table in the set of conversion tables is used to find the location of the page tables in the real memory. The proper page table is then used to find the real location of the addressed page. The byte portion of a virtual address refers to a real location in memory so that once the segment and page portions of the virtual address have been translated to give a page location the byte portion is concatenated onto the page location to give the real address in main storage.
To avoid having to translate an address each time the memory is accessed, current translations of virtual addresses to real addresses are retained in another table called the Directory Look Aside Table (DLAT) where such addresses can be obtained with a virtual address without going through the described translation process. The use of the DLAT significantly reduces the number of translation that must be made and thus has a considerable effect on the performance of the virtual memory system.
Multiple sets of tables are used to generate the translations stored in the DLAT. One problem with this is that it could result in the selection of an incorrect translation from the DLAT. To assure that the conversion table used in deriving the real addresses stored in the DLAT are the same as those tables used in deriving the real addresses of the data currently being paged, it has been suggested in U.S. Pat. No 3,781,808 filed on Dec. 25, 1973 and assigned to the same assignee as the present invention that an identifier be stored in the DLAT along with each translation. In Ahearn et al U.S. Pat. No. 3,781,808 entitled "Virtual Memory System" this identifier is a 3 digit number that signifies the set of tables used in making the translation. In interrogating the DLAT this stored identifier is compared with an identifier generated for the currently requested virtual address. If the virtual address and identifiers of the currently requested address match those for a translation stored in the DLAT, the translation stored in the DLAT may be used. If the identifiers or virtual addresses do not match a new translation must be performed using the set of conversion tables associated with the currently requested address. This identifier can also be used to distinguish between virtual addresses having different page and segment sizes and, in addition, can be used to indicate that a real address is being employed instead of a virtual address.
Another case where an incorrect translation can be used is where for a number of reasons the entries in the DLAT are invalid. When this happens the DLAT must be purged by an invalidation or purge instruction. One solution to purging the DLAT is to have invalid bits stored with each translation in the DLAT invalidation. When a purge instruction occurs these bits are reset to indicate that the instruction is invalid. However this takes a significant length of time. Every time an invalid instruction is received by the memory all the entries have to be read out one at a time and written back into the DLAT in order to reset the valid bits. This is a very slow process.